142.环形链表 II

142. 环形链表 II 题解

---

题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

---

思路

采用快慢指针的思路，但此法妙在如何计算head和环开始节点之间的距离。

声明两个指针，一个fast，一个slow。fast指针每次走两步，slow指针每次走一步。

那么会有两种情况：

一、如果fast走到了nullptr，那么就说明这个链表没有环

二、如果有环，那么fast和slow一定会会相遇，这便是第一次相遇

第一次相遇时我们记录然后退出，接下来思考如何计算得出环的第一个节点。

这是我们现在的情况

那么我们怎么求a呢？

假设slow指针前进的距离为x，那么fast指针前进的距离为2x
所以我们能得出：x = a+b

而fast比slow多走的距离，恰好就是环的长度，也就是c
所以，我们能得到等式：x = c

所以a+b = c a = c-b

a就是start到node的距离，c-b就是slow指针还剩下的没走的环的距离

所以，我们让fast = start，fast++的同时slow++

当fast和slow第二次相遇时，就是node的位置

---

代码

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast=head,*slow=head;
        
        while(true){
            if(fast==nullptr || fast->next==nullptr)return nullptr;
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow) break;
        }
        fast=head;
        while(fast!=slow){
            slow=slow->next;
            fast=fast->next;
        }
        return fast;
    }
};

---

结束

小技巧，妙不可言…